package paixu;

public class InsertSort {
    public static void main(String[] args) {
        int arr[] = new int[]{17, 3, 25, 14, 20, 9};
        int i = 1;
        while (i < arr.length) {
            int insertVal = arr[i];
            int insertIndex = i - 1;
            i++;
            //insertIndex >= 0 保证在给insertVal 找到插入的位置，不越界
            //insertVal < arr[insertIndex] 待插入的数，还没有找到插入位置
            //就需要将arr[insertIndex]后移动 再将insertIndex-- 比较已经入列的arr[insertIndex]与insertVal
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {//核心
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            //为什么是 insertIndex+1
            // 3 17 25 14  i=3 insertIndex=2 14<25? insertIndex-- insertIndex=1
            // 14<17? insertIndex-- insertIndex=0 此时 14<3? 不是 此时找到插入位置为 3的前一个 因此是insertIndex+1
            if(insertIndex+1 != i){
                arr[insertIndex + 1] = insertVal;
            }
            for (int j = 0; j < arr.length; j++) {
                System.out.print("  "+arr[j]);
            }
            System.out.println();
        }
    }
}